There are numerous examples of data records to which interval queries, such as time interval, may be applied. In an online advertisement context, anonymized data may be collected for online users. Data may be collected for various user online activities, such as user interactions with respect to online advertisements, as well as other types of online interactions. The stored user data is typically associated with various time intervals for various user interactions. Other applications that may include the storage of large amounts of time interval data include television, telecom, and customer support interactions.